#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

void process(const std::vector<int>& a) {
	for(int i = 0; i < a.size(); ++i){
		for (int j = 0; j < a.size(); ++j){
			if (j == a[i])
				std::cout << "1";
			else
				std::cout << "0";
		}
		std::cout << std::endl;
	}
	std::cout << std::endl;
}
void generate_candidates(const std::vector<int>& a, int k, int n, std::queue<int>& q){
	for (int i = 0; i < n; ++i){
		bool valid = true;
		for (int j = 0; j < k; ++j) {
			if (a[j] == i) {
				valid = false;
				break;
			}
			int row_distance = k - j;
			int column_distance = abs(i-a[j]);
			if(row_distance == column_distance) {
				valid = false;
				break;
			}
		}
		if(valid)
			q.push(i);
	}
}
//a[i] stores the ith queen is placed in a[i]th column, n = a.size();
int backtrack(std::vector<int>& a, int k, int n){
	if(k == n) {
		process(a);
		return 1;
	}
	else {
		int count = 0;
		std::queue<int> q;
		generate_candidates(a,k,n,q);
		while(!q.empty()){
			int c = q.front();
			q.pop();
			a[k] = c;
			count += backtrack(a,k+1,n);
		}
		return count;
	}
}

void test_9_9(){
	std::vector<int> a(8);
	std::cout << "There are " << backtrack(a,0,a.size()) << " ways\n";
}